// https://www.lintcode.com/problem/search-in-rotated-sorted-array-ii/

public class Solution {
    /**
     * @param A: an integer ratated sorted array and duplicates are allowed
     * @param target: An integer
     * @return: a boolean 
     */
    public boolean search(int[] A, int target) {
        // write your code here
        int start = 0, end = A.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (A[mid] == target) {
                return true;
            }
            int m1 = mid, m2 = mid;
            while ((m1 > start) && (A[m1] <= A[start])) {
                --m1;
                if (A[m1] == target) {
                    return true;
                }
            }
            while ((m2 < end) && (A[m2] >= A[end])) {
                ++m2;
                if (A[m2] == target) {
                    return true;
                }
            }
            if ((A[m1] >= target) && (A[start] <= target)) {
                end = m1 - 1;
            } else if ((A[m2] <= target) && (A[end] >= target)) {
                start = m2 + 1;
            } else {
                break;
            }
        }
        return false;
    }
}